package com.example.tree.heap;

import java.util.ArrayList;
import java.util.List;

public class TestTrie {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.addWord("love");
        trie.addWord("am");
        trie.addWord("hh");
        trie.addWord("live");

        for (String word : trie.getWords()) {
            System.out.println(word);
        }


    }

    private static class Trie {
        private TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void addWord(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                int pos = word.charAt(i) - 'a';
                if (cur.children[pos] == null) {
                    cur.children[pos] = new TrieNode();
                }
                cur = cur.children[pos];
            }
            cur.word = word;

        }

        public List<String> getWords() {
            List<String> res = new ArrayList<>();
            getWords(this.root, res);
            return res;
        }

        public void getWords(TrieNode root, List<String> res) {
            if (root == null) {
                return;
            }
            if (root.word != null) {
                res.add(root.word);
            }

            for (int i = 0; i < 26; i++) {
                if (root.children[i] != null) {
                    getWords(root.children[i], res);
                }
            }
        }

        class TrieNode {
            TrieNode[] children;
            String word;

            public TrieNode() {
                children = new TrieNode[26];
                word = null;
            }
        }
    }

    //构建trie树
//    static class Trie2 {
//        TrieNode root = new TrieNode();
//        public void addWord(String word){
//            TrieNode cur = root;
//            for(char c:word.toCharArray()){
//                if(cur.children[c-‘a’]==null){ cur.children[c-'a'] = new TrieNode();}
//                cur = cur.children[c-'a'];
//            }
//            cur.word = word;
//        }
//        //对于每个桶中同样频率的单词，用DFS得到字典序顺序
//        public void getWords(TrieNode root, List<String> ans){
//            if(root ==null){return;}
//            if(root.word!=null){ans.add(root.word);}
//            for(int i = 0;i<=25;i++){
//                if(root.children[i]!=null){ getWords(root.children[i], ans);}
//            }
//        }
//        class TrieNode {//定义TrieNode
//            TrieNode[] children;
//            String word;
//            TrieNode() {
//                this. children = new TrieNode[26];
//                this.word = null;
//            }
//        }
}
